Grokking Tree Coding Patterns for Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Course Overview
Basics of Tree
Introduction to Tree
Types of Tree
BST Traversal Techniques
BST Operations
Level Order Traversal Pattern (easy)
Introduction to Level Order Traversal Pattern
Reverse Level Order Traversal (easy)
Solution: Reverse Level Order Traversal
Find Largest Value in Each Tree Row (medium)
Solution: Find Largest Value in Each Tree Row
Maximum Width of Binary Tree (medium)
Solution: Maximum Width of Binary Tree
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Zigzag Traversal (medium)
Solution: Zigzag Traversal
Even Odd Tree (medium)
Solution: Even Odd Tree
N-ary Tree Level Order Traversal (hard)
Solution: N-ary Tree Level Order Traversal
Introduction to Tree Depth Pattern
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Balanced Binary Tree (easy)
Solution: Balanced Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Maximum Depth of N-ary Tree (easy)
Solution: Maximum Depth of N-ary Tree
Find maximum depth of subtree (medium)
Solution: Find maximum depth of subtree
Introduction to Root to Leaf Path Pattern
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Sum of Root To Leaf Binary Numbers (easy)
Solution: Sum of Root To Leaf Binary Numbers
Insufficient Nodes in Root to Leaf Paths (medium)
Solution: Insufficient Nodes in Root to Leaf Paths
Smallest String Starting From Leaf (medium)
Solution: Smallest String Starting From Leaf
Pseudo-Palindromic Paths in a Binary Tree (medium)
Solution: Pseudo-Palindromic Paths in a Binary Tree
All Paths for a Sum (medium)
Solution: All Paths for a Sum
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Path With Given Sequence (medium)
Solution: Path With Given Sequence
Count Paths for a Sum (medium)
Solution: Count Paths for a Sum
Introduction to Leaf Processing Pattern
Sum of Left Leaves (easy)
Solution: Sum of Left Leaves
Leaf-Similar Trees (easy)
Solution: Leaf-Similar Trees
Check if all leaves are at same level (medium)
Solution: Check if all leaves are at same level
Delete Leaves With a Given Value (medium)
Solution: Delete Leaves With a Given Value
Deepest Leaves Sum (medium)
Solution: Deepest Leaves Sum
Introduction to Tree View Pattern
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Top View Of the Binary Tree (medium)
Solution: Top View Of the Binary Tree
Bottom View Of the Binary Tree (medium)
Solution: Bottom View Of the Binary Tree
Boundary of Binary Tree (medium)
Solution: Boundary of Binary Tree
Introduction to Comparison of Two Trees Pattern
Symmetric Tree (easy)
Solution: Symmetric Tree
Mirror Image Trees (medium)
Solution: Mirror Image Trees
Subtree of Another Tree (easy)
Solution: Subtree of Another Tree
Isomorphic Trees (medium)
Solution: Isomorphic Trees
Introduction to Serialize and Deserialize Tree Pattern
Serialize and Deserialize BST (medium)
Solution: Serialize and Deserialize BST
Verify Preorder Serialization of a Binary Tree (medium)
Solution: Verify Preorder Serialization of a Binary Tree
Create Binary Tree From Descriptions (medium)
Solution: Create Binary Tree From Descriptions
Serialize and Deserialize N-ary Tree (hard)
Solution: Serialize and Deserialize N-ary Tree
Solution: N-ary Tree Level Order Traversal

Problem Statement

Given an n-ary tree, return a list representing the level order traversal of the nodes' values in this tree.

The input tree is serialized in an array format using level order traversal, where the children of each node are grouped together and separated by a null value.

Examples

Example 1

  • Input: root = [1, null, 2, 3, 4, null, 5, 6]
Image
  • Expected Output: [[1], [2, 3, 4], [5, 6]]
  • Justification: The root node 1 is at level 0. Nodes 2, 3, and 4 are the children of 1 and are at level 1. Nodes 5 and 6 are the children of 2, and at level 3.

Example 2

  • Input: root = [7, null, 3, 8, 5, null, 2, 9, null, 6, null, 1, 4, 10]
Image
  • Expected Output: [[7], [3, 8, 5], [2, 9, 6, 1, 4, 10]]
  • Justification: The root node 7 is at level 0. Nodes 3, 8, and 5 are its children at level 1. Nodes 2, 9, 6, 1, 4, and 10 are at level 2.

Example 3

  • Input: root = [10, null, 15, 12, null, 20, null, 25, null, 30, 40]
Image
  • Expected Output: [[10], [15, 12], [20, 25], [30, 40]]
  • Justification: The root node 10 is at level 0. Nodes 15 and 12 are its children at level 1. Node 20 and 25 are at level 2. Nodes 30, and 40 are at level 3.

Constraints:

  • The height of the n-ary tree is less than or equal to 1000
  • The total number of nodes is between [0, 104]

Solution

To solve this problem, we use a queue-based approach to perform a level order traversal of the n-ary tree. The main idea is to process all nodes level by level, starting from the root. We use a queue to keep track of nodes at each level. At each step, we remove nodes from the queue, record their values, and add their children to the queue. This ensures that we traverse all nodes at the current level before moving to the next.

This approach is effective because it processes each node exactly once, which makes it efficient with a time complexity of , where N is the total number of nodes in the tree. The use of a queue helps manage nodes level by level, ensuring that the output is correctly grouped. By storing nodes of each level in a separate list, we maintain the order of traversal and construct the desired output format.

Step-by-Step Algorithm

  1. Initialize Result and Queue:

    • Create an empty list result to store the final output.
    • If root is null, return the empty result.
    • Initialize a queue and add the root node to it.
  2. Level Order Traversal:

    • While the queue is not empty:
      • Determine the number of nodes at the current level (size).
      • Create an empty list level for the current level values.
      • For each node at the current level:
        • Remove the node from the queue and add its value to level.
        • Add all children of the node to the queue.
      • Add level to the result.
  3. Return Result:

    • Return the result containing all level values.

Algorithm Walkthrough

For the input root = [1, null, 2, 3, 4, null, 5, 6]:

  1. Initialize:
    Start by creating an empty list result = [] to store the output and a queue initialized with the root node: queue = [1].

  2. First Level:

    • The size of the current level is size = 1 (only the root node).
    • Create an empty list for this level: level = [].
    • Dequeue the first node, 1, from the queue, and add its value to level: level = [1].
    • Enqueue its children, 2, 3, 4, into the queue: queue = [2, 3, 4].
    • Add the level list to the result: result = [[1]].
  3. Second Level:

    • The size of the current level is size = 3 (nodes 2, 3, 4).
    • Create an empty list for this level: level = [].
    • Dequeue node 2 from the queue, add its value to level: level = [2], and enqueue its children 5, 6: queue = [3, 4, 5, 6].
    • Dequeue node 3, add its value to level: level = [2, 3] (node 3 has no children).
    • Dequeue node 4, add its value to level: level = [2, 3, 4] (node 4 has no children).
    • Add the level list to the result: result = [[1], [2, 3, 4]].
  4. Third Level:

    • The size of the current level is size = 2 (nodes 5, 6).
    • Create an empty list for this level: level = [].
    • Dequeue node 5 from the queue, add its value to level: level = [5] (node 5 has no children).
    • Dequeue node 6, add its value to level: level = [5, 6] (node 6 has no children).
    • Add the level list to the result: result = [[1], [2, 3, 4], [5, 6]].
  5. Completion:

    • The queue is now empty, which means all levels have been processed.
    • Return the result: [[1], [2, 3, 4], [5, 6]].

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • The algorithm traverses each node in the n-ary tree exactly once.
  • For each node, the algorithm processes its children, which involves adding them to the queue.
  • Thus, the total time complexity is , where N is the total number of nodes in the tree.

Space Complexity

  • The queue may store up to nodes at the widest level of the tree, where W is the maximum width of the tree.
  • Therefore, the space complexity is in the worst case, which occurs when the tree is a balanced tree or has a large number of nodes at the same level.
N-ary Tree Level Order Traversal (hard)
Introduction to Tree Depth Pattern
Mark as Completed

On this page

Problem Statement

Examples

Example 1

Example 2

Example 3

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity